package com.fengdi.solutions.hard;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author FengDi
 * @Description 239 滑动窗口最大值
 * */
public class _239_Sliding_window_maximum {

    public int[] maxSlidingWindow(int[] nums, int k) {

        if(nums.length == 0 || k == 0) return new int[0];

        ArrayList<Integer> result = new ArrayList<Integer>(); // result of algorithm
        Deque<Integer> queue = new ArrayDeque<>(); // sliding window

        for(int i = 1 - k, j = 0; j < nums.length; i++, j++) {
            if( i > 0 && queue.peekFirst() == nums[i - 1]) queue.removeFirst();
            while(!queue.isEmpty() && queue.peekLast() < nums[j]) queue.removeLast();
            queue.addLast(nums[j]);

            if( i >= 0) {
                result.add(queue.peekFirst());
            }
        }

        return result.stream().mapToInt(i -> i).toArray();

    }
}
